//////////////////////////////////////////////////////////////////////////////////
//                                                                              //
//  This file is part of the buola project (https://code.google.com/p/buola/).  //
//                                                                              //
//  Copyright(c) 2007-2011 Xavi Gratal                                          //
//  gratal AT gmail DOT com                                                     //
//                                                                              //
//  Buola is free software: you can redistribute it and/or modify               //
//  it under the terms of the GNU General Public License as published by        //
//  the Free Software Foundation, either version 3 of the License, or           //
//  (at your option) any later version.                                         //
//                                                                              //
//  Buola is distributed in the hope that it will be useful,                    //
//  but WITHOUT ANY WARRANTY; without even the implied warranty of              //
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the               //
//  GNU General Public License for more details.                                //
//                                                                              //
//  You should have received a copy of the GNU General Public License           //
//  along with buola.  If not, see <http://www.gnu.org/licenses/>.              //
//                                                                              //
//////////////////////////////////////////////////////////////////////////////////

#ifndef _BUOLA_ALGORITHM_SPLIT_H_
#define _BUOLA_ALGORITHM_SPLIT_H_

#include <buola/functors/predicates/char.h>
#include <buola/iterator/range.h>
#include <buola/iterator/facade.h>
#include <buola/iterator/end.h>

namespace buola {

///\addtogroup algorithm
///@{

///\name Split
//@{

///splits the string \p pSrc into tokens, separated by delimiters

///A delimiter is any character for which the predicate function \p pPred returns \e true.
///
///The matching tokens are inserted into \p pDst, which must be a container which can contain objects
///which can be initialized from a pair of iterators to \p tSrc.
template<typename tSrc,typename tDst,typename tPred>
void split(const tSrc &pSrc,tDst &pDst,tPred pPred)
{
    auto i=range_begin(pSrc);
    auto lEnd=range_end(pSrc);
    auto s=i;
    while(i!=lEnd)
    {
        if(pPred(*i))
        {
            pDst.emplace_back(s,i);
            s=++i;
        }
        else
        {
            ++i;
        }
    }
    pDst.emplace_back(s,i);
}

///splits the string \p pSrc into tokens, separated by delimiters

///A delimiter is any character for which the predicate function \p pPred returns \e true.
///
///The matching tokens are inserted into \p pDst, which must be a container which can contain objects
///which can be initialized from a pair of iterators to \p tSrc.
///
///This overload doesn't insert empty elements into the destination container. Empty elements occur
///when there are leading, trailing or consecutive delimiters
template<typename tSrc,typename tDst,typename tPred>
void split(const tSrc &pSrc,tDst &pDst,tPred pPred,NDeleteEmpty)
{
    auto i=range_begin(pSrc);
    auto lEnd=range_end(pSrc);
    auto s=i;
    while(i!=lEnd)
    {
        if(pPred(*i))
        {
            if(s!=i)
                pDst.emplace_back(s,i);
            s=++i;
        }
        else
        {
            ++i;
        }
    }
    if(s!=i)
        pDst.emplace_back(s,i);
}

/////////////////////////////////////////////////////////////////////////////////////////////////

/// split iterator

/// This iterator can be used to iterate over parts of a container, separated by the given
/// delimiter.
///
/// When dereferencing, an iterator range over the original sequence is returned.
///
/// For examples, see the helper function \ref split_begin
///
/// \tparam tMode can be NDefault or NDeleteEmpty, which has the same meaning as for \ref split
///
/////////////////////////////////////////////////////////////////////////////////////////////////

template<typename tIt,typename tPred,typename tMode>
class ISplit : public IFacade<ISplit<tIt,tPred,tMode>,std::forward_iterator_tag,const CRange<tIt>>
{
    friend class IFacade<ISplit<tIt,tPred,tMode>,std::forward_iterator_tag,const CRange<tIt>>;

    typedef CRange<tIt> tMatch;
    
public:
    ///default constructor (invalid iterator)
    ISplit() {}
    
    ///copy constructor
    ISplit(const ISplit &pO)
        :   mNext(pO.mNext)
        ,   mEnd(pO.mEnd)
        ,   mEof(pO.mEof)
        ,   mPred(pO.mPred)
    {}
    
    ///initializes an end-of-input iterator
    ISplit(const IEnd&)
        :   mEof(true)
    {
    }
    
    ///initializes the iterator
    
    ///The resulting iterator can be used to iterate over the substrings of [\p pB,\p pE), separated by
    ///elements for which \p pPred returns \c true
    ISplit(tIt pB,tIt pE,const tPred &pPred)
        :   mNext(pB)
        ,   mEnd(pE)
        ,   mEof(false)
        ,   mPred(pPred)
    {
        IncrementImpl(tMode(),true);
    }
    
private:
    ///returns the current match
    const tMatch &Dereference() const
    {
        return mMatch;
    }

    ///advances to the next match (default implementation)
    void IncrementImpl(NDefault,bool pFirst)
    {
        if(mNext==mEnd)
        {
            if(pFirst)
                mMatch=tMatch(mNext,mNext);
            else
                mEof=true;
            return;
        }
        if(!pFirst)
            ++mNext;
        tIt lBegin=mNext;
        
        while(mNext!=mEnd)
        {
            if(mPred(*mNext))
                break;

            ++mNext;
        }
        
        mMatch=tMatch(lBegin,mNext);
        //we leave the iterator pointing at the delimiter
    }
    
    ///advances to the next match (delete-empty implementation)
    void IncrementImpl(NDeleteEmpty,bool)
    {
        while(mNext!=mEnd)
        {
            if(!mPred(*mNext)) //our sequence begins here
            {
                tIt lBegin=mNext;
                ++mNext;
                while(mNext!=mEnd)
                {
                    if(mPred(*mNext))
                    {
                        mMatch=tMatch(lBegin,mNext++);
                        return;
                    }
                    ++mNext;
                }
                
                mMatch=tMatch(lBegin,mNext);
                return;
            }
            
            ++mNext;
        }
        
        mEof=true;
    }

    ///advances to the next match
    void Increment()
    {
        IncrementImpl(tMode(),false);
    }
    
    ///compares two split iterators
    bool Equal(const ISplit &pO) const
    {
        if(mEof||pO.mEof) return mEof==pO.mEof;
        
        return mNext==pO.mNext&&mEnd==pO.mEnd;
    }
    
    ///compares this iterator to the end-of-input iterator
    bool Equal(const IEnd&) const
    {
        return mEof;
    }
    
    tIt mNext,mEnd;
    tMatch mMatch;
    bool mEof;
    tPred mPred;
};

///returns an iterator that can be used to iterate over the given range

///Unlike other iterators, the iterator returned by \c range_begin contains the whole range
///over which it iterates, while \c range_end contains no information, and is just useful to
///compare it with exhausted ISplit iterators.
///
///For example, if \c lString is a string,
///\code
///for(auto i=split_begin(lString,fn::is_space());i!=split_end();++i)
///{
///    msg_info() << i->end()-i->begin() << "\n";
///}
///\endcode
///
///would print the length of all substrings of lString separated by whitespace
template<typename tRange,typename tPred,typename tMode=NDefault>
inline auto split_begin(tRange &pRange,tPred pPred,tMode=nDefault)
                    -> ISplit<decltype(range_begin(pRange)),tPred,tMode>
{
    return ISplit<decltype(range_begin(pRange)),tPred,tMode>(range_begin(pRange),range_end(pRange),pPred);
}

///returns an end-of-input iterator

///It can be compared to other split iterators to know if the input has been exhausted.
inline IEnd split_end()
{
    return IEnd();
}

//@}

///@}

/*namespace buola*/ }

#endif
